package codeTop;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class q47 {
    public List<List<Integer>> permuteUnique1(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            list.add(11);
        }
        Arrays.sort(nums);
        List<int[]> map = new ArrayList<>();
        for (int num : nums) {
            if (!map.isEmpty() && map.get(map.size() - 1)[0] == num) {
                map.get(map.size()-1)[1]++;
            }else {
                map.add(new int[]{num,1});
            }
        }
        dfs1(map,res,list,0,0,0);
        return res;
    }

    private void dfs1(List<int[]> map, List<List<Integer>> res, List<Integer> list, int idx,int cnt,int start) {
        if (idx==map.size()) {
            res.add(List.copyOf(list));
            return;
        }
        for (int i = start; i < list.size(); i++) {
            if (list.get(i) == 11) {
                list.set(i,map.get(idx)[0]);
                if (cnt == map.get(idx)[1] - 1) {
//                    dfs(map,res,list,idx+1,0,0);
                }else {
//                    dfs(map,res,list,idx,cnt+1,i+1);
                }
                list.set(i,11);
            }
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] flags = new boolean[n];
        dfs(nums,res,list,flags,0);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, List<Integer> list, boolean[] flags, int cnt) {
        if (cnt == nums.length) {
            res.add(List.copyOf(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!flags[i] && !(i > 0 && nums[i] == nums[i - 1] && !flags[i - 1])) {
                list.add(nums[i]);
                flags[i] = true;
                dfs(nums, res, list, flags, cnt+1);
                list.remove(list.size()-1);
                flags[i] = false;
            }
        }
    }
}
